不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入：3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

提示：

  • 0 <= n <= 8

代码：

0时57空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
    	List<TreeNode> ls=new ArrayList<TreeNode>();
    	//初始化表
    	int[] table=new int[n];
    	for(int i=1;i<=n;i++)
    	{
    		table[i-1]=i;
    	}
    	//递归生成
//    	for(int i=0;i<n;i++)
//    	{
//    		//分割两块
//    		int[] low=Arrays.copyOf(table,i);
//    		int[] high=Arrays.copyOfRange(table,i+1,table.length);
//    		System.out.println(Arrays.toString(low));
//    		System.out.println(Arrays.toString(high));
//    	}
    	ls=core(table,n);
    	return ls;
    }
    
    public List<TreeNode> core(int[] table,int n)
    {
    	List<TreeNode> sum=new ArrayList<TreeNode>();
    	//递归生成
    	for(int i=0;i<n;i++)
    	{
    		List<TreeNode> lt=new ArrayList<TreeNode>();
        	List<TreeNode> rt=new ArrayList<TreeNode>();
    		//分割两块
    		int[] low=Arrays.copyOf(table,i);
    		int[] high=Arrays.copyOfRange(table,i+1,table.length);
    		if(low.length==0)
    		{
    			lt.add(null);
    		}else if(low.length==1)
    		{
    			lt.add(new TreeNode(low[0]));
    		}else
    		{
    			lt=core(low,low.length);
    		}
    		
    		if(high.length==0)
    		{
    			rt.add(null);
    		}else if(high.length==1)
    		{
    			rt.add(new TreeNode(high[0]));
    		}else
    		{
    			rt=core(high,high.length);
    		}
    		
    		for(int li=0;li<lt.size();li++)
    			for(int ri=0;ri<rt.size();ri++)
    			{
    				sum.add(new TreeNode(table[i],lt.get(li),rt.get(ri)));
    				//System.out.println("输出一个"+table[i]+" 左右值"+lt.get(li)+rt.get(ri));
    			}
    	}
    	return sum;
    }
}